package com.atguigu.substring;

public class RabinKarp {
    public static final long seed=31;
    public static long hash(String str){
        long res=0;
        for(int i=0;i<str.length();i++){
            res=31*res+str.charAt(i);
        }
        return res;
    }
    public static long[] hash(String str,int M){ //M为str2的长度
        long[] res=new long[str.length()-M];
        //先计算0-M的hash值
        res[0]=hash(str.substring(0,M));
        //开始滚动
        for(int i=M;i<str.length();i++){
            char newChar=str.charAt(i);
            char oldChar=str.charAt(i-M);
            long v=(res[i-M]*31+newChar-(long)Math.pow(31,M)*oldChar)%Long.MAX_VALUE; //%是为了防止溢出
            res[i-M+1]=v;
        }
        return res;
    }
}
